/**
 * @description 堆排序
 * @param {*} arr 
 * @returns 
 */
const heapsort = arr => {
    // 克隆数组
    const a = [...arr];
    let l = a.length;
  
    // 使用闭包来封装，建立大顶堆的函数
    const heapify = (a, i) => {
      const left = 2 * i + 1;
      const right = 2 * i + 2;
      let max = i;
      if (left < l && a[left] > a[max]) max = left;
      if (right < l && a[right] > a[max]) max = right;
      if (max !== i) {
        [a[max], a[i]] = [a[i], a[max]];
        // 递归调用
        heapify(a, max);
      }
    };
  
    // 初始化创建最大堆
    for (let i = Math.floor(l / 2); i >= 0; i -= 1) heapify(a, i);

    // 反复缩小考虑的范围进行排序
    for (i = a.length - 1; i > 0; i--) {
        // [ 6, 1 ]
        // [ 4, 1 ]
        // [ 3, 1 ]
        console.log([a[0], a[i]]);
        [a[0], a[i]] = [a[i], a[0]];
        l--;
      heapify(a, 0);
    }
    // 最后返回排序好的克隆数组 a
    return a;
  };
  // 例子
heapsort([6, 3, 4, 1]); // [1, 3, 4, 6]